﻿#define _CRT_SECURE_NO_WARNINGS 1
/*

给你一个整数数组 heights ，表示建筑物的高度。另有一些砖块 bricks 和梯子 ladders 。

你从建筑物 0 开始旅程，不断向后面的建筑物移动，期间可能会用到砖块或梯子。

当从建筑物 i 移动到建筑物 i+1（下标 从 0 开始 ）时：

如果当前建筑物的高度 大于或等于 下一建筑物的高度，则不需要梯子或砖块
如果当前建筑的高度 小于 下一个建筑的高度，您可以使用 一架梯子 或 (h[i+1] - h[i]) 个砖块
如果以最佳方式使用给定的梯子和砖块，返回你可以到达的最远建筑物的下标（下标 从 0 开始 ）。
*/

//
//
//extern void insertHeapNode(int *heap, int *heapSize, int diff);
//extern void replaceHeapNode(int *heap, int heapSize, int diff);
//
//int furthestBuilding(int *heights, int heightsSize, int bricks, int ladders)
//{
//    int x = 0, diff = 0, heapSize = 0;
//    /* 考虑到ladders允许取0，所以加1以保证小根堆的长度不为0，实际只有前面ladders个是有效的。 */
//int heap[ladders + 1];
//
//while (heightsSize - 1 > x)
//{
//    /* 只有下一栋建筑比当前建筑更高时，才有必要使用砖块或梯子，否则可以直接跳过去。 */
//    if (heights[x + 1] > heights[x])
//    {
//        diff = heights[x + 1] - heights[x];
//        /* 梯子还没用完时，先使用梯子。 */
//        if (ladders > heapSize)
//        {
//            insertHeapNode(heap, &heapSize, diff);
//        }
//        /* 否则考虑是直接使用砖块，还是和已使用过的梯子交换。 */
//        else
//        {
//            /* 如果梯子总数为0，或者当前diff不比小根堆里面的最小值要大，则当前diff只能使用砖块。 */
//            if (0 == heapSize || diff <= heap[0])
//            {
//                /* 剩余砖块数量不够时，到此为止。 */
//                if (bricks < diff)
//                {
//                    break;
//                }
//                bricks -= diff;
//            }
//            /* 否则考虑和前面小根堆里面最小的diff交换一下梯子。 */
//            else
//            {
//                /* 但是如果剩余砖块数量连那个最小diff也填不满的话，也只能到此为止。 */
//                if (bricks < heap[0])
//                {
//                    break;
//                }
//                /* 砖块要匀出对应数量，来交换前面那个使用过的梯子。 */
//                bricks -= heap[0];
//                replaceHeapNode(heap, heapSize, diff);
//            }
//        }
//    }
//    x++;
//}
//
//return x;
//}
//
///* 把新的差值加入到堆中，放的时候要把较大的数值先往下层放。 */
//void insertHeapNode(int* heap, int* heapSize, int diff)
//{
//    int son = *heapSize, father = (0 == son) ? -1 : (son - 1 >> 1);
//
//    while (-1 != father && diff < heap[father])
//    {
//        heap[son] = heap[father];
//        son = father;
//        father = (0 == son) ? -1 : (son - 1 >> 1);
//    }
//    heap[son] = diff;
//    (*heapSize)++;
//
//    return;
//}
//
///* 用新的差值替换堆顶的数值，放的时候要把较小的子节点数值调上来。 */
//void replaceHeapNode(int* heap, int heapSize, int diff)
//{
//    int father = 0, left = 1, right = 2, swap = 0;
//
//    while ((heapSize > left && heap[left] < diff)
//        || (heapSize > right && heap[right] < diff))
//    {
//        swap = (heapSize > right && heap[left] > heap[right]) ? right : left;
//        heap[father] = heap[swap];
//        father = swap;
//        left = (father << 1) + 1;
//        right = (father << 1) + 2;
//    }
//    heap[father] = diff;
//
//    return;
//}


/*
给你一个字符串 s ，请你找到 s 中两个 不相交回文子序列 ，使得它们长度的 乘积最大 。两个子序列在原字符串中如果没有任何相同下标的字符，则它们是 不相交 的。

请你返回两个回文子序列长度可以达到的 最大乘积 。

子序列 指的是从原字符串中删除若干个字符（可以一个也不删除）后，剩余字符不改变顺序而得到的结果。如果一个字符串从前往后读和从后往前读一模一样，那么这个字符串是一个 回文字符串 。

*/

//
//int maxProduct(char* s)
//{
//    const int length = strlen(s), maxMask = (1 << length) - 1;
//    int x = 0, mask1 = 1, mask2 = 0, i = 0, j = 0, bufferSize = 0, t = 0, complementary = 0, former = 0, result = 0;
//    char buffer[length];
//
//    // 子集mask1非空，所以从1开始遍历。
//    while (maxMask > mask1)
//    {
//        // 列出子集mask1的字符。
//        // 由于mask1是循环变量，不要中途修改掉，把它赋值给临时变量t来计算。
//        x = 0;
//        bufferSize = 0;
//        t = mask1;
//        while (0 != t)
//        {
//            if (1 & t)
//            {
//                buffer[bufferSize] = s[x];
//                bufferSize++;
//            }
//            x++;
//            t = t >> 1;
//        }
//        // 查看子集mask1是否回文子序列。
//        i = 0;
//        j = bufferSize - 1;
//        while (i < j && buffer[i] == buffer[j])
//        {
//            i++;
//            j--;
//        }
//        // 当子集mask1是回文子序列时，再看它的补集里面的最长回文子序列。
//        if (i >= j)
//        {
//            // 先把刚才子集mask1的长度记录下来，放到former变量中。
//            // 把mask1的补集complementary列出，遍历它的所有子集。
//            former = bufferSize;
//            complementary = maxMask & ~mask1;
//            mask2 = complementary;
//            while (0 < mask2)
//            {
//                // 列出补集complementary的子集mask2的字符。
//                // 同上，由于mask2是循环变量，不能中途改变掉，所以赋值给临时变量t。
//                x = 0;
//                bufferSize = 0;
//                t = mask2;
//                while (0 != t)
//                {
//                    if (1 & t)
//                    {
//                        buffer[bufferSize] = s[x];
//                        bufferSize++;
//                    }
//                    x++;
//                    t = t >> 1;
//                }
//                // 查看子集mask2是否回文子序列。
//                i = 0;
//                j = bufferSize - 1;
//                while (i < j && buffer[i] == buffer[j])
//                {
//                    i++;
//                    j--;
//                }
//                // 当complementary的子集mask2也是回文子序列，且两者长度乘积更大时，更新结果。
//                if (i >= j && result < former * bufferSize)
//                {
//                    result = former * bufferSize;
//                }
//                // complementary的下一个子集。
//                // 这里用一个与操作，是加快循环速度，且确保它是complementary的子集。
//                mask2 = mask2 - 1 & complementary;
//            }
//        }
//        // 下一个子集。
//        mask1++;
//    }
//
//    return result;
//}